package com.my.ds.impl.stack;

/**
 * 基于链表实现的链式栈
 * <p>
 * 参考：<a href="https://blog.csdn.net/Real_Fool_/article/details/113852222">数据结构：栈和队列(Stack & Queue)【详解】</a>
 *
 * @author: marshal
 * @date: 2023-02-17 10:10
 */
public class LinkedStack {
    /**
     * 带头哨兵
     */
    private final Node head = new Node();

    /**
     * 栈的大小
     */
    private int size;

    /**
     * 链表节点
     */
    private class Node {
        public int data;
        public Node next;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }
    }


    /**
     * 入栈
     *
     * @param data 元素
     * @return true/false
     */
    public boolean push(int data) {
        Node newNode = new Node(data);
        Node h = head;
        // 找出尾节点
        while (h.next != null) {
            h = h.next;
        }
        // 将尾节点的next指针指向新的节点
        h.next = newNode;
        ++size;
        return true;
    }

    /**
     * 出栈
     *
     * @return 出栈的数据
     */
    public int pop() {
        // 拿到最后一个节点数据,并返回
        Node h = head;
        // 找到倒数第二个节点
        for (int i = 0; i < size - 1; i++) {
            h = h.next;
        }
        // 把它的下一个节点的数据返回,同时删除这个节点
        int result = h.next.data;
        h.next = null;
        --size;
        return result;
    }
}
